package gold.gold05;

import java.util.Arrays;

/**
 *
 */
public class S1706_2出现的次数 {
    /**
     * 100, 大家时间都一样。总数应该不会超过2^32。尝试找一下数学规律。
     * 算出每个位数上的每个数字所能含有的2, 然后计算一下每一位, 注意当前位为2时比较特殊。
     */
    public int numberOf2sInRange(int n) {
        // 这个函数调用不建议放在for的判断里面, 因为每次判断都会调用一次。
        int maxPlace = getMaxPlace(n) + 1;
        int[][] record = new int[maxPlace][10];
        record[0] = new int[]{0, 0, 1, 0, 0, 0, 0, 0, 0, 0};
        for(int i = 1; i < record.length; i++){
            int[] temp1 = new int[10];
            Arrays.fill(temp1, arraySum(record[i - 1], 10));
            temp1[2] += (int)Math.pow(10, i);
            record[i] = temp1;
        }
        int res = 0;
        // 获取每个位数上的值, 待优化。
        for(int i = 0; i < maxPlace; i++){
            int curNum = n / (int)Math.pow(10, maxPlace - 1 - i);
            n -= curNum * (int)Math.pow(10, maxPlace - 1 - i);
            res += arraySum(record[maxPlace - 1 - i], curNum);
            if(curNum == 2) res += (n + 1);
        }
        return res;
    }
    // 这是几位数
    public int getMaxPlace(int n){
        int res = 0;
        while((n = n / 10) > 0) // 这种表示方式是可以的。
            res ++;
        return res;
    }
    // endPosi不取
    public int arraySum(int[] nums, int endPosi){
        int res = 0;
        for(int i = 0; i < endPosi; i++)
            res += nums[i];
        return res;
    }

    /**
     * 体面的别人的代码。
     * 这个从低位到高位, 非常巧妙。
     */
    public int numberOf2sInRange2(int n) {
        int digit = 1, res = 0;
        // cur为从低到高的位数, high为剩下的高位, low为n-high, digit为当前位(10, 100, 1000这样)。
        int cur = n % 10, high = n / 10, low = 0;
        while(high != 0 || cur != 0) {
            if(cur < 2)
                res += high * digit;
            else if(cur == 2)
                res += high * digit + low + 1;
            else
                res += (high + 1) * digit;
            low = low + cur * digit;
            cur = high % 10;
            high = high / 10;
            digit = digit * 10;
        }
        return res;
    }

}
